package own.stu.jobgib.playown.alg.leetcode.editor.cn.demo;

import java.util.*;

import static own.stu.jobgib.playown.alg.leetcode.editor.cn.demo.Helper.format;
import static own.stu.jobgib.playown.alg.leetcode.editor.cn.demo.LargeFileComparator.getInts;
import static own.stu.jobgib.playown.alg.leetcode.editor.cn.demo.LargeFileComparator.getInts2;

public class Demo3_binary {
    public static void main(String[] args) {

        /*System.out.println(search(new int[]{5,7,7,8,8,10}, 8));
        System.out.println(search3(new int[]{5,7,7,8,8,10}, 8));

        System.out.println(search(new int[]{5,7,7,8,8,10}, 5));
        System.out.println(search3(new int[]{5,7,7,8,8,10}, 5));

        System.out.println(search(new int[]{5,7,7,8,8,10}, 10));
        System.out.println(search3(new int[]{5,7,7,8,8,10}, 10));


        System.out.println(search(new int[]{5,7,7,8,8,10}, 4));
        System.out.println(search3(new int[]{5,7,7,8,8,10}, 4));


        System.out.println(search(new int[]{5,7,7,8,8,10}, 15));
        System.out.println(search3(new int[]{5,7,7,8,8,10}, 15));*/

//        Arrays.stream(searchRange(new int[]{5,7,7,8,8,10}, 8)).forEach(System.out::print);
//        Arrays.stream(searchRange(new int[]{1}, 1)).forEach(System.out::print);

//        System.out.println(searchInsert(new int[]{1,3,5,6}, 2));

//        System.out.println(nextGreatestLetter(new char[]{'c', 'f', 'j'}, 'a'));

//        System.out.println(maximumCount(new int[]{-2,-1,-1,1,2,3}));


//        System.out.println(maximumCount(new int[]{-3,-2,-1,0,0,1,2}));

        /*int[] ints = getInts2("/Users/qim/Documents/idea-code/play-own/src/main/resources/xxx/1.txt");
        int[] ints2 = getInts2("/Users/qim/Documents/idea-code/play-own/src/main/resources/xxx/2.txt");
        successfulPairs(ints, ints2, 9505642132L);*/

//        Arrays.stream(numSmallerByFrequency(new String[]{"cbd"}, new String[]{"zaaaz"})).forEach(System.out::print);
//        Arrays.stream(numSmallerByFrequency(new String[]{"bbb","cc"}, new String[]{"a","aa","aaa","aaaa"})).forEach(System.out::print);

//        Arrays.stream(numSmallerByFrequency(new String[]{"bba","abaaaaaa","aaaaaa","bbabbabaab","aba","aa","baab","bbbbbb","aab","bbabbaabb"},
//                new String[]{"aaabbb","aab","babbab","babbbb","b","bbbbbbbbab","a","bbbbbbbbbb","baaabbaab","aa"})).forEach(System.out::print);

//        System.out.println(solveQueries(new int[]{1,3,1,4,1,3,2}, new int[]{0,3,5}));

//        System.out.println(countFairPairs(new int[]{0,4,4,5,7}, 3, 6 ));

        /*int[][] format = format("[[193,732],[781,962],[864,954],[749,627],[136,746],[478,548],[640,908],[210,799],[567,715],[914,388],[487,853],[533,554],[247,919],[958,150],[193,523],[176,656],[395,469],[763,821],[542,946],[701,676]]");
        Arrays.stream(maximumBeauty(format, new int[]{885,1445,1580,1309,205,1788,1214,1404,572,1170,989,265,153,151,1479,1180,875,276,1584})).forEach(System.out::println);*/

        /*FIFOCache<Integer, Integer> map = new FIFOCache<>(3);
        map.put(2,2);
        map.put(1, 1);
        map.put(3,3);
        System.out.println(map);
//        System.out.println(map.getFirstKey().get());
        map.get(1);
        System.out.println(map);
//        System.out.println(map.getFirstKey().get());
        map.get(2);
//        System.out.println(map.getFirstKey().get());*/

        //["Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"]
        //[[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]
        Router2 router = new Router2(3);
        router.addPacket(1, 4, 90);
        router.addPacket(2, 5, 90);
        router.addPacket(1, 4, 90);
        router.addPacket(3, 5, 95);
        router.addPacket(4, 5, 105);
        int[] ints = router.forwardPacket();
        System.out.println(Arrays.toString(ints));
        router.addPacket(5, 2, 110);
        int cnt = router.getCount(5, 100, 110);
        System.out.println(cnt);

     }

    static class Router2 {
        private record Packet(int source, int destination, int timestamp) {
        }

        private record Pair(List<Integer> timestamps, int head) {
        }

        private final int memoryLimit;
        private final Queue<Packet> packetQ = new ArrayDeque<>(); // Packet 队列
        private final Set<Packet> packetSet = new HashSet<>(); // Packet 集合
        private final Map<Integer, Pair> destToTimestamps = new HashMap<>(); // destination -> ([timestamp], head)

        public Router2(int memoryLimit) {
            this.memoryLimit = memoryLimit;
        }

        public boolean addPacket(int source, int destination, int timestamp) {
            Packet packet = new Packet(source, destination, timestamp);
            if (!packetSet.add(packet)) { // packet 在 packetSet 中
                return false;
            }
            if (packetQ.size() == memoryLimit) { // 太多了
                forwardPacket();
            }
            packetQ.add(packet); // 入队
            destToTimestamps.computeIfAbsent(destination, k -> new Pair(new ArrayList<>(), 0)).timestamps.add(timestamp);
            return true;
        }

        public int[] forwardPacket() {
            if (packetQ.isEmpty()) {
                return new int[]{};
            }
            Packet packet = packetQ.poll(); // 出队
            packetSet.remove(packet);
            destToTimestamps.compute(packet.destination, (k, p) -> new Pair(p.timestamps, p.head + 1)); // 队首下标加一，模拟出队
            return new int[]{packet.source, packet.destination, packet.timestamp};
        }

        public int getCount(int destination, int startTime, int endTime) {
            Pair p = destToTimestamps.get(destination);
            if (p == null) {
                return 0;
            }
            int left = lowerBound(p.timestamps, startTime, p.head - 1);
            int right = lowerBound(p.timestamps, endTime + 1, p.head - 1);
            return right - left;
        }

        // https://www.bilibili.com/video/BV1AP41137w7/
        private int lowerBound(List<Integer> nums, int target, int left) {
            int right = nums.size();
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                if (nums.get(mid) >= target) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            return right;
        }
    }

    static class Router {
        FIFOCache<Key, Object> cache;
        Map<Integer, List<Integer>> map = new HashMap<>();
        public Router(int memoryLimit) {
            cache = new FIFOCache<>(memoryLimit);
        }

        public boolean addPacket(int source, int destination, int timestamp) {
            return cache.put(new Key(source, destination, timestamp), null) == null;
        }

        public int[] forwardPacket() {
            Key firstKey = cache.getFirstKey();
            if(firstKey != null){
                return new int[]{firstKey.source, firstKey.destination, firstKey.timestamp};
            }
            return new int[]{};
        }

        public int getCount(int destination, int startTime, int endTime) {
            return 0;
        }

        static class Key{
            int source;
            int destination;
            int timestamp;
            public Key(int source, int destination, int timestamp) {
                this.source = source;
                this.destination = destination;
                this.timestamp = timestamp;
            }

            @Override
            public boolean equals(Object o) {
                if(o == this) return true;
                if(o == null || getClass() != o.getClass()) return false;
                Key key = (Key) o;
                return source == key.source && destination == key.destination && timestamp == key.timestamp;
            }

            @Override
            public int hashCode() {
                return Objects.hash(source, destination, timestamp);
            }
        }
    }

    public static class FIFOCache<K, V> extends LinkedHashMap<K, V> {
        private final int maxSize;

        public FIFOCache(int maxSize) {
            super(maxSize, 0.75f, true); // false 表示按插入顺序，不是访问顺序
            this.maxSize = maxSize;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize; // 当大小超过限制时，移除最老的元素
        }

        public Map.Entry<K, V> getFirstEntry() {
            if (isEmpty()) {
                return null;
            }
            return entrySet().iterator().next();
        }

        // 获取第一个键
        public K getFirstKey() {
            Map.Entry<K, V> firstEntry = getFirstEntry();
            return firstEntry == null ? null : firstEntry.getKey();
        }
    }

    static class TimeMap {

        Map<String, List<Pari>> map = new HashMap<>();
        public TimeMap() {

        }

        public void set(String key, String value, int timestamp) {
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pari(timestamp, value));
        }

        public String get(String key, int timestamp) {
            List<Pari> paris = map.get(key);
            if(paris == null){
                return "";
            }
            int idx = help(paris, timestamp);
            return idx < 0 ? "" : paris.get(idx).val;
        }

        private int help(List<Pari> list, int t){
            int l = -1, r = list.size();
            while(l + 1 < r){
                int mid = l + (r - l) / 2;
                if(list.get(mid).t <= t){
                    l = mid;
                }else{
                    r = mid;
                }
            }
            return l;
        }

        public static class Pari{
            public int t;
            public String val;
            public Pari(int t, String val) {
                this.t = t;
                this.val = val;
            }
        }
    }

    static class SnapshotArray {

        private int curSnapId;

        Map<Integer, List<int[]>> map = new HashMap<>();

        public SnapshotArray(int length) {

        }

        public void set(int index, int val) {
            List<int[]> ints = map.computeIfAbsent(index, k -> new ArrayList<>());
            ints.add(new int[]{curSnapId, val});
        }

        public int snap() {
            return curSnapId++;
        }

        public int get(int index, int snap_id) {
            List<int[]> ints = map.get(index);
            if(ints == null){
                return 0;
            }
            int l = 0, r = ints.size() - 1;
            int j = help(ints, snap_id);
            return j < 0 ? 0 : ints.get(j)[1];
        }

        private int help(List<int[]> list, int t){
            int l = -1, r = list.size();
            while(l + 1 < r){
                int mid = l + (r - l) / 2;
                if(list.get(mid)[0] <= t){
                    l = mid;
                }else{
                    r = mid;
                }
            }
            return l;
        }
    }

    static class SnapshotArray2 {
        int[] curSnap;
        int[] nums;
        List<int[]> snapshots;

        public SnapshotArray2(int length) {
            nums = new int[ length];
            snapshots = new ArrayList<>();
        }

        public void set(int index, int val) {
            nums[index] = val;
            curSnap = null;
        }

        public int snap() {
            if(curSnap == null){
                curSnap = Arrays.copyOf(nums, nums.length);
            }
            snapshots.add(curSnap);
            return snapshots.size() - 1;
        }

        public int get(int index, int snap_id) {
            return snapshots.get(snap_id)[index];
        }
    }

    public static int[] maximumBeauty(int[][] items, int[] queries) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int[] item : items) {
            map.merge(item[0], item[1], Math::max);
        }
        int curMax = 0;
        for (Integer i : map.keySet()) {
            curMax = Math.max(curMax, map.get(i));
            map.put(i, curMax);
        }

        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            Map.Entry<Integer, Integer> entry = map.floorEntry(queries[i]);
            if(entry == null){
                ans[i] = 0;
            }else {
                ans[i] = entry.getValue();
            }
        }
        return ans;
    }

    private static int helper6(int[][] item, int target) {
        int l = -1, r = item.length;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (item[mid][0] >= target) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }

    /**
     * 如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
     * 0 <= i < j < n，且
     * lower <= nums[i] + nums[j] <= upper
     *
     * 无论i < j 还是 j < i ,如果 lower <= nums[i] + nums[j] <= upper 都是满足结果的，所以 nums 可以排序
     *
     *  lower - nums[j] <= nums[i] <= upper - nums[j]
     *  对于 某个 j， 需要在[0, j -1] 范围中 找到  <=（upper-nums[j])的个数 - <（lower-nums[j])的个数
     *
     *  1 找到 > (uppper - nums[j])的第一个数，下标为r，那么[0, r-1]都是 <=（uppper - nupms[j])，有r个，如果没有找个数，那么结果是j,
     *  那么意味着[0,j-1]中都是 <=（upper - nupms[j])，有j个。
     *  2 找到 >= (lower - nums[j])的第一个数，下标为l,那么[0, l -1]都是 <(lower-nums[j])的，有l个。没有找到，那么结果是j,
     *  那么意味着[0,j-1]中都是 <(lower-nums[j])的，有j个。
     *
     *
     */
    public static long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        int n = nums.length;
        long ans = 0;
        for(int j = 0; j < n; j ++){
            int r = helper6(nums, j, upper - nums[j] + 1);
            int l = helper6(nums, j, lower - nums[j]);
            ans += r - l;
        }
        return ans;
    }

    private static int helper6(int[] nums, int r, int target){
        int l = -1;
        while(l + 1 < r){
            int mid = l + (r - l) / 2;
            if(nums[mid] >= target){
                r = mid;
            }else{
                l = mid;
            }
        }
        return r;
    }

    public static List<Integer> solveQueries(int[] nums, int[] queries) {

        if(queries == null || nums == null || queries.length == 0){
            return new ArrayList<>();
        }

        List<Integer> ans = new ArrayList<>(queries.length);

        int n = nums.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }
        for (List<Integer> pList : map.values()) {
            if(pList.size() > 1){
                Integer idx = pList.get(0);
                pList.add(0, pList.get(pList.size() - 1) - n);
                pList.add(idx + n);
            }
        }

        for(int i: queries){
            List<Integer> pList = map.get(nums[i]);
            if(pList.size() == 1){
                ans.add(-1);
            }else{
                int idx = Collections.binarySearch(pList, i);
                ans.add(Math.min(i - pList.get(idx - 1), pList.get(idx + 1) - i));
            }
        }
        return ans;
    }

    static class RangeFreqQuery {

        Map<Integer, List<Integer>> map = new HashMap<>();
        public RangeFreqQuery(int[] arr) {
            for(int i = 0; i < arr.length; i++){
                map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
            }
        }

        public int query(int left, int right, int value) {
            List<Integer> poses = map.get(value);
            if(poses == null || poses.size() == 0){
                return 0;
            }
            return helper6(poses, right + 1) - helper6(poses, left);
        }
    }

    private static int helper6(List<Integer> list, int target){
        int l = -1, r = list.size();
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if(list.get(mid) >= target){
                r = mid;
            }else{
                l = mid;
            }
        }
        return r;
    }

    public static int[] numSmallerByFrequency(String[] queries, String[] words) {
        if(queries == null || queries.length == 0 || words == null || words.length == 0){
            return new int[]{};
        }
        int n = queries.length, m = words.length;
        int[] qn = new int[n];
        int[] wm = new int[m];
        int[] map = new int[26];
        for(int i = 0; i < n; i++){
            qn[i] = build(queries[i], map);
        }
        for(int i = 0; i < m; i++){
            wm[i] = build(words[i], map);
        }
        Arrays.sort(wm);
        for(int i = 0; i < n; i++){
            qn[i] = m - helper5(wm, qn[i]);
        }
        return qn;
    }

    private static int helper5(int[] nums, int target){
        int l = -1, r = nums.length;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if(nums[mid] > target){
                r = mid;
            }else {
                l = mid;
            }
        }
        return r;
    }

    private static int build(String q, int[] map){
        Arrays.fill(map, 0);
        for(char c : q.toCharArray()){
            map[c - 'a']++;
        }
        for(int i = 0; i < 26; i++){
            if(map[i] != 0){
                return map[i];
            }
        }
        return 0;
    }

    public static int[] answerQueries(int[] nums, int[] queries) {
        if(nums == null || nums.length == 0 || queries == null || queries.length == 0){
            return new int[]{};
        }
        int[] ans = new int[queries.length];
        Arrays.sort(nums);
        for(int i = 1; i < nums.length; i++){
            nums[i] = nums[i] + nums[i - 1];
        }
        int m = queries.length;
        for(int i = 0; i < m; i++){
            ans[i] = helper4(nums,queries[i]);
        }
        return ans;
    }

    private static int helper4(int[] nums, int target) {
        int l = -1, r = nums.length;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if(nums[mid] > target){
                r = mid;
            }else {
                l = mid;
            }
        }
        return r;
    }


    public static int[] successfulPairs(int[] spells, int[] potions, long success) {
        if(spells == null || spells.length == 0 || potions == null || potions.length == 0){
            return new int[]{};
        }
        int n = spells.length, m = potions.length;
        for(int i = 0; i < n; i++){
            spells[i] = (int)((spells[i] + success - 1) / spells[i]);
        }
        Arrays.sort(potions);
        int[] ans = new int[n];
        for(int i = 0; i < n; i ++){
            ans[i] = m - helper3(potions, spells[i]);
        }
        return ans;
    }

    private static int helper3(int[] nums, int target){
        int l = -1, r = nums.length;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if(nums[mid] >= target){
                r = mid;
            }else {
                l = mid;
            }
        }
        return r;
    }

    public static int maximumCount(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int n = nums.length;
        int idx = helper2(nums, 0); //最左边的大于等于0的下标
        int pos = n - helper2(nums, 1);
        return Math.max(pos, idx);
    }

    private static int helper2(int[] nums, int target){
        int l = -1, r = nums.length;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if(nums[mid] >= target){
                r = mid;
            }else {
                l = mid;
            }
        }
        return r;
    }

    public static char nextGreatestLetter(char[] letters, char target) {
        if(letters == null || letters.length == 0){
            return ' ';
        }
        int idx = helper1(letters, (char)(target + 1));
        if(idx == -1 || idx == letters.length){
            return letters[0];
        }
        return letters[idx];
    }

    private static int helper1(char[] nums, char target) {
        int l = -1, r = nums.length;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if(nums[mid] >= target){
                r = mid;
            }else {
                l = mid;
            }
        }
        return r;
    }


    public static int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int l = 0, r = nums.length - 1;
        while(l + 1 < r){
            int mid = l + (r - l) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                l = mid;
            }else{
                r = mid;
            }
        }
        if(nums[l] > target){
            return l;
        }
        if(nums[r] > target){
            return r;
        }
        return r + 1;
    }

    public static int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return new int[]{-1, -1};
        }
        int x = search3(nums, target);
        if(x == -1 || nums[x] != target){
            return new int[]{-1, -1};
        }
        return new int[]{x, search3(nums, target + 1) - 1};
    }

    // 二分查找 返回最小满足 nums[i] >= target 的 i
    public static int search(int[] nums, int target) {
        // 闭区间
        int l = 0;
        int r = nums.length - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return l;
    }

    public static int search3(int[] nums, int target) {
        // 开区间
        int l = 0;
        int r = nums.length - 1;
        while(l + 1< r){
            int mid = l + (r - l) / 2;
            if(nums[mid] < target){
                l = mid;
            }else{
                r = mid;
            }
        }
        if(nums[l] >= target) return l;
        if(nums[r] >= target) return r;
        return -1;
    }

    public static int search4(int[] nums, int target) {
        // 开区间
        int l = -1;
        int r = nums.length;
        while(l + 1< r){
            int mid = l + (r - l) / 2;
            if(nums[mid] < target){
                l = mid;
            }else{
                r = mid;
            }
        }
        /*if(nums[l] >= target) return l;
        if(nums[r] >= target) return r;
        return -1;*/
        return r;
    }
}